Библиотека собеса по Java | вопросы с собеседований

Алгоритм Кнута — Морриса — Пратта

Алгоритм КМП осуществляет поиск текста по заданному шаблону. В этом поиске сначала компилируется заданный шаблон. Компилируя шаблон, мы пытаемся найти префикс и суффикс строки шаблона. Это поможет в случае несоответствия — не придётся искать следующее совпадение с начального индекса.

Вместо этого мы пропускаем часть текстовой строки, которую уже сравнили, и начинаем сравнивать следующую. Необходимая часть определяется по префиксу и суффиксу, поэтому известно, какая часть уже прошла проверку и может быть безопасно пропущена.

👍6

www.tg-me.com/pl/Библиотека собеса по Java | вопросы с собеседований/com.java_interview_lib/325

7.85K viewsMar 24, 2024 at 18:09

Алгоритм Кнута — Морриса — Пратта

Алгоритм КМП осуществляет поиск текста по заданному шаблону. В этом поиске сначала компилируется заданный шаблон. Компилируя шаблон, мы пытаемся найти префикс и суффикс строки шаблона. Это поможет в случае несоответствия — не придётся искать следующее совпадение с начального индекса.

Вместо этого мы пропускаем часть текстовой строки, которую уже сравнили, и начинаем сравнивать следующую. Необходимая часть определяется по префиксу и суффиксу, поэтому известно, какая часть уже прошла проверку и может быть безопасно пропущена.

BY Библиотека собеса по Java | вопросы с собеседований